<html>
<head><meta charset="utf-8"><title>Alternative `Relation` representations · t-compiler/wg-polonius · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/index.html">t-compiler/wg-polonius</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html">Alternative `Relation` representations</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="221365937"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221365937" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221365937">(Jan 01 2021 at 19:51)</a>:</h4>
<p>I alluded to this in <a class="stream-topic" data-stream-id="186049" href="/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Optimization.20PRs">#t-compiler/wg-polonius &gt; Optimization PRs</a>, but I don't see a fundamental reason why <code>Relation</code>s must be stored as lists of tuples. Am I missing something? One obstacle is the fact that <code>Leaper</code> currently operates on <code>Vec&lt;&amp;'_ Val&gt;</code> instead of <code>Vec&lt;Val&gt;</code>, but this can be changed (see <a href="https://github.com/rust-lang/datafrog/issues/19">rust-lang/datafrog#19</a>).</p>



<a name="221366068"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221366068" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221366068">(Jan 01 2021 at 19:54)</a>:</h4>
<p>We spend a lot of time binary searching <code>cfg_edge</code> while running the initialization rules, and I suspect there's other dense relations that would benefit from <code>O(1)</code> lookup on their keys</p>



<a name="221372072"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221372072" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221372072">(Jan 01 2021 at 22:27)</a>:</h4>
<p>I don't think there are fundamental reasons for that, just that it's easy to implement a datafrog engine that way</p>



<a name="221372084"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221372084" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221372084">(Jan 01 2021 at 22:27)</a>:</h4>
<p>some context which might be important: I think Frank did most of this in a weekend or something</p>



<a name="221372138"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221372138" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221372138">(Jan 01 2021 at 22:28)</a>:</h4>
<p>and that was enough to be better than using DD (both in compile time and running time)</p>



<a name="221372453"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221372453" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221372453">(Jan 01 2021 at 22:37)</a>:</h4>
<p>Leapers did seem to offer a way to separate the representation (or at least offer a way to make different representations work together), but now that I think about it I've only experimented with different relations for antijoins with bloom and counting quotient filters, without changing or abstracting the representation. This impression was probably wrong, I didn't even hit the API snag you mention</p>



<a name="221373243"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221373243" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221373243">(Jan 01 2021 at 22:57)</a>:</h4>
<p>(also note: the move/init rules you mention above are incomplete, probably contain bugs, and are currently doing more work than necessary; albin and niko worked on them last sprint in this thread <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/move.20error.20reporting">https://rust-lang.zulipchat.com/#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/move.20error.20reporting</a> if you're interested in them specifically)</p>



<a name="221374799"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221374799" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221374799">(Jan 01 2021 at 23:39)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116113">lqd</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Alternative.20.60Relation.60.20representations/near/221372084">said</a>:</p>
<blockquote>
<p>some context which might be important: I think Frank did most of this in a weekend or something</p>
</blockquote>
<p>Souffle also doesn't use an "adjacency list" representation, it's BTrees or a custom radix tree (called a brie), so it's not just datafrog, but point taken.</p>



<a name="221523817"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221523817" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221523817">(Jan 04 2021 at 13:40)</a>:</h4>
<p>if we're optimizing binary search, I was thinking some <code>Relation</code>s could also benefit from having a different layout while still using the same representation, like using van Emde Boas or Eytzinger layouts (classic paper from pvk <a href="https://arxiv.org/abs/1509.05053">https://arxiv.org/abs/1509.05053</a>) for our joins with static inputs</p>



<a name="221581571"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221581571" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221581571">(Jan 04 2021 at 21:14)</a>:</h4>
<p>I wonder how much time we spend doing range queries vs. single-element lookups. sorted lists are optimal in terms of instructions  once the first element is found, and should be close to cache-optimal as well. I wonder how vEB trees or B-trees stack up here.</p>



<a name="221581640"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221581640" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221581640">(Jan 04 2021 at 21:14)</a>:</h4>
<p>Also, I wonder how much of datafrog's performance is due to the way the <code>stable</code> part of a variable is optimized for writes</p>



<a name="221581791"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221581791" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221581791">(Jan 04 2021 at 21:15)</a>:</h4>
<p>(Not sure what to call the list of sorted lists with exponentially increasing lengths, it's kinda like an in-memory log-structured merge tree I guess?)</p>



<a name="221581913"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221581913" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221581913">(Jan 04 2021 at 21:16)</a>:</h4>
<p>It's gotta be a lot faster than writing to the middle of a B-tree.</p>



<a name="221582259"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221582259" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221582259">(Jan 04 2021 at 21:19)</a>:</h4>
<p>(One of the optimizations I was gonna investigate was a larger minimum capacity for  the smallest list in <code>stable</code>. It should be a cache-line's worth of data, but I think it's 1 right now?)</p>



<a name="221582695"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221582695" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221582695">(Jan 04 2021 at 21:22)</a>:</h4>
<p>Anyways, I'm kind of off optimizing datafrog right now. Time would be better spent adding features (arithmetic predicates, automatic stratification, etc.) IMO.</p>



<a name="221583391"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221583391" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221583391">(Jan 04 2021 at 21:28)</a>:</h4>
<p>it very well could be</p>



<a name="221583594"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Alternative%20%60Relation%60%20representations/near/221583594" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Alternative.20.60Relation.60.20representations.html#221583594">(Jan 04 2021 at 21:30)</a>:</h4>
<p>(esp. if it were to be used in rustc for some of the various analyses?)</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>